<?php
/**
 * @title 1545. 找出第 N 个二进制字符串中的第 K 位 - 对称
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param Integer $n
     * @param Integer $k
     * @return String
     */
    function findKthBit($n, $k) {
        /**
         * @since 2020-08-11 结果集
         */
        $result = "0";

        /**
         * @since 2020-08-11 正反
         */
        $sign = true;

        /**
         * @since 2020-08-11 Sn字符串长度
         */
        $len = pow(2, $n)-1;

        /**
         * @since 2020-08-11 对半查找
         */
        while($len > 1){
            /**
             * @since 2020-08-11 一半
             */
            $half = $len>>1;

            /**
             * @since 2020-08-11 中间点
             */
            $mid = $half+1;
            // echo "len={$len}, k={$k}, mid={$mid}", PHP_EOL;

            /**
             * @since 2020-08-11 中间点
             */
            if($k == $mid){
                $result = "1";
                break;
            } elseif($k<$mid) {
                /**
                 * @since 2020-08-11 左半段
                 */
            } else {
                /**
                 * @since 2020-08-11 右半段
                 */
                $k = $len-$k+1;
                $sign = !$sign;
            }

            /**
             * @since 2020-08-11 对半长度
             */
            $len = $half;
        }

        /**
         * @since 2020-08-11 是否对称点, 取反
         */
        if(!$sign){
            $result = strval(intval(!$result));
        } else {}

        /**
         * @return
         */
        return $result;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.11_3.php
 */
$datas = [
    // [3,1],
    [4,11],
    // [1,1],
    // [2,3],
    // [3,5],
    // [2,1],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->findKthBit($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
